public class Offer_42 {
    /**
     * 剑指 Offer 42. 连续子数组的最大和
     */

    public int maxSubArray(int[] nums) {
        int res = nums[0];
        for (int i = 1; i < nums.length; i++) {
            res = getRes(nums, res, i);
        }
        return res;
    }

    private int getRes(int[] nums, int res, int i) {
        nums[i] += Math.max(nums[i -1],0);
        res = Math.max(res, nums[i]);
        return res;
    }

    public static void main(String[] args) {
        int[] nums = {-2,1,-3,4,-1,2,1,-5,4};
        Offer_42 offer = new Offer_42();
        System.out.println(offer.maxSubArray(nums));
    }
}
